The present invention relates to a method of transforming into vectors a map, diagram or similar graphic line image which is implemented as a two-level digital image.
The recognition of various kinds of drawings such as a machine drawing and a logic circuit diagram has been extensively studied as means for automatically inputting graphic data to a CAD/CAM system and is now in a practical stage for some subjects to be dealt with. One of the fundamental techniques enabling the recognition of this kind of graphic image is the transformation of a raster image into vectors, i.e., approximating a linear portion of an input image by a vector that extends through the center thereof. This technique plays the most important role in the recognition of a drawing because it not only implements the analysis of an input image but also allows the resultant graphic data to be compressed or otherwise processed.
Methods heretofore proposed for generating vector data from a two-level image read by a digital scanner may generally be classified into two types, i.e., a method of the type using raster operations and a method of the type determining a center line out of a contour line. Typical of the raster operation type method is a skeltonizing procedure. The skeltonizing procedure is such that an input image having a line width of three dots is sequentially reduced, one dot at a time, until the line width decreases to one dot, and the so skeltonized image is approximated by vectors. On the other hand, the center line type procedure is such that, assuming that an input image also has a line width of three dots, a contour line of one dot is traced in one direction and approximated by straight lines to produce contour vectors, and then vector pairs each defining opposite sides of the resultant line figure are detected to determine their center lines. For details of the center line type procedure, a reference may be made to a paper entitled "Figure Processing Using Multi-Dimension Data Structure-- Transformation of Figure into Vectors", The Institute of Electronics and Communication Engineers of Japan, Collected Papers, Vol. J68D, No. 4, Apr. 1985. The method disclosed in this paper promotes rapid and flexible processing despited the use of software and produces information associated with the line width and the intersection of lines during the course of processing. Also, the proposed method enhances rapid extraction of vector pairs by supervising contour vectors on a multi-dimension data structure basis.
A problem with the skeltonizing scheme, however, is that it needs substantial processing time although it preserves the connections of the original figure. Another problem is that rapid processing is not achievable without resorting to special-purpose hardware which would limit the flexibility of processing and add to cost. Further, skeltonization needs a memory having a large capacity and is apt to entail various kinds of noise. While the center line scheme is free from such problems, it has a drawback that vectors are segmented in those portions of an image where lines intersect each other.